This paper studies the computational complexity of the Edge Packing problemand the Vertex Packing problem. The edge packing problem (denoted by$\bar{EDS}$) and the vertex packing problem (denoted by $\bar{DS} $) are linearprogramming duals of the edge dominating set problem and the dominating setproblem respectively. It is shown that these two problems are equivalent to theset packing problem with respect to hardness of approximation and parametriccomplexity. It follows that $\bar{EDS}$ and $\bar{DS}$ cannot be approximatedasymptotically within a factor of $O(N^{1/2-\epsilon})$ for any $\epsilon>0$unless $NP=ZPP$ where, $N$ is the number of vertices in the given graph. Thisis in contrast with the fact that the edge dominating set problem is2-approximable where as the dominating set problem is known to have an $O(\log$$|V|)$ approximation algorithm. It also follows from our proof that $\bar{EDS}$and $\bar{DS}$ are $W[1]$-complete.
展开▼
机译：本文研究了Edge Packing问题和Vertex Packing问题的计算复杂性。边缘堆积问题（用$ \ bar {EDS} $表示）和顶点堆积问题（用$ \ bar {DS} $表示）分别是边缘控制集问题和控制集问题的线性规划对偶。结果表明，就近似硬度和参数复杂性而言，这两个问题等同于设定堆积问题。因此，对于任何$ε> 0 $，除非$$，否则$ \ bar {EDS} $和$ \ bar {DS} $不能在$ O（N ^ {1 / 2- \ epsilon}）$因子内近似地渐近。 NP = ZPP $其中，$ N $是给定图中顶点的数量。这与以下事实相反：边缘控制集问题是2近似的，而已知控制集问题具有$ O（\ log $$ | V |）$近似算法。从我们的证明还可以得出，$ \ bar {EDS} $和$ \ bar {DS} $是完整的$ W [1] $。
展开▼
